import java.util.Stack;

public class Sort {
    public void SelectSort(int[] array) {
        int left = 0, right = array.length - 1;
        while (left < right) {
            int maxIndex = right;
            int minIndex = left;
            for (int i = left + 1; i < right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array, left, minIndex);
            if (left == maxIndex) {
                maxIndex = minIndex;
            }
            swap(array, right, maxIndex);
            left++;
            right--;
        }
    }

    public void InsertSort(int[] array) {
        int len = array.length;
        for (int i = 1; i < len; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    public void HeapSort(int[] array) {


    }

    private void siftdown(int[] array) {

    }

    public void ShellSort(int[] array) {
        int len = array.length;
        int gap = len;
        while (gap > 1) {
            gap = gap / 3 + 1;
            for (int i = gap; i < len; i++) {
                int tmp = array[i];
                int j = 0;
                for (j = i - gap; j >= 0; j -= gap) {
                    if (array[j] > tmp) {
                        array[j + gap] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + gap] = tmp;
            }
        }
    }

    //三数取中
    int GetMinIndex(int[] a, int left, int right) {
        int mid = (left + right) / 2;
        if (a[left] < a[mid]) {
            if (a[mid] < a[right]) {
                return mid;
            } else if (a[left] < a[right]) {
                return right;
            } else {
                return left;
            }
        } else {
            if (a[mid] < a[right]) {
                return mid;
            } else if (a[left] > a[right]) {
                return right;
            } else {
                return left;
            }
        }
    }

    //hero
    public void QuickSort1(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int midi = GetMinIndex(array, begin, end);
        swap(array, begin, midi);
        int keyi = begin;
        int left = begin, right = end;
        while (left < right) {
            while (left < right && array[right] >= array[keyi]) {
                right--;
            }
            while (left < right && array[left] <= array[keyi]) {
                left++;
            }
            swap(array, right, left);
        }
        swap(array, keyi, right);
        QuickSort1(array, begin, left - 1);
        QuickSort1(array, left + 1, end);
    }

    //挖坑法
    public void QuickSort2(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int midi = GetMinIndex(array, begin, end);
        swap(array, begin, midi);
        int key = array[begin];
        int hole = begin;
        int left = begin;
        int right = end;
        while (left < right) {
            while (left < right && array[right] >= key) {
                right--;
            }
            array[hole] = array[right];
            hole = right;

            while (left < right && array[left] <= key) {
                left++;
            }
            array[hole] = array[left];
            hole = left;
        }
        array[hole] = key;
        QuickSort2(array, begin, left - 1);
        QuickSort2(array, left + 1, end);
    }


    //前后指针法
    public void QuickSort3(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int midi = GetMinIndex(array, begin, end);
        swap(array, begin, midi);
        int keyi = begin;
        int prev = begin, cur = begin + 1;
        while (cur <= end) {
            if (array[cur] <= array[keyi]) {
                prev++;
                if (cur != prev) {
                    swap(array, cur, prev);
                }
            }
            cur++;
        }
        swap(array, keyi, prev);

        QuickSort3(array, begin, prev - 1);
        QuickSort3(array, prev + 1, end);
    }


    //前后指针法排序一次
    private int PartSort(int[] a, int begin, int end) {
        int mid = GetMinIndex(a, begin, end);
        swap(a, begin, mid);
        int prev = begin, cur = begin + 1;
        int keyi = begin;
        while (cur <= end) {
            if(a[cur] <a[keyi]) {
                prev++;
                if(cur!=prev) {
                    swap(a,cur,prev);
                }
            }
            cur++;
        }
        swap(a,keyi,prev);
        return prev;
    }

    //快速排序非递归
    public void QuickSortNonR(int[] array, int begin, int end) {
        Stack<Integer> stack = new Stack<>();
        stack.push(end);
        stack.push(begin);

        while (!stack.isEmpty()) {
            int left = stack.pop();
            int right = stack.pop();
            int keyi = PartSort(array,left,right);
            if(keyi+1<right) {
                stack.push(right);
                stack.push(keyi+1);
            }
            if(left<keyi-1) {
                stack.push(keyi-1);
                stack.push(left);
            }
        }
    }

    public void MergeSort(int[] array,int begin,int end) {

    }

    private void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

}
